\section{Implementing detectors and analyses}

\subsection{Fundamental concepts}

\input{slides/FindBugsConcepts1}

\input{slides/ProjectConcept}

\input{slides/AnalysisCacheConcept}

\input{slides/ClassMethodDescriptorConcept}

\input{slides/DetectorConcept}

\input{slides/AnalysisPassConcept}

\input{slides/BugInstanceConcept}

\input{slides/BugReporterConcept}

\input{slides/BugCollectionConcept}

%\subsection{FindBugs algorithm}

\input{slides/FindBugsAlgorithmIntro}

\input{slides/FindBugsAlgorithm}

\input{slides/FindBugsAlgorithmDetails}

\input{slides/WritingDetectorsIntro}

%\PlaceholderSlide{Demo plugin}{Where to find it, etc.}
\Slide{Demo plugin}{
  \B
  \item {\tt demopluginsrc\_start.zip}: empty ``starting point'' plugin
  \item {\tt demopluginsrc\_finished.zip}: the completed demo plugin
  \item Demo plugin must be checked out in sibling directory of
        main FindBugs source dist
    \B
    \item Recommended: use Eclipse
    \E
  \item Demo plugin code is in public domain
    \B
    \item You are encouraged to use it as the basis for your own plugins
    \item Just change package names and other identifying information
          so that it does not conflict with {\tt edu.umd.cs.findbugs.*}
          and {\tt net.findbugs.*}
    \E
  \E
}

\input{slides/WritingDetectorsSteps}

\subsection{Plugin structure}

\TitleSlide{Plugin structure}

\input{slides/PluginConcept}
\input{slides/PluginOverview}

\input{slides/PluginDescriptorSkeleton}

\input{slides/MessagesFileSkeleton}

\subsection{Micropattern detector}

\TitleSlide{Micropattern detector}

\input{slides/MicropatternExampleIntro}

\input{slides/MicropatternAddDetectorClass}

\input{slides/MicropatternBoilerplate}

\input{slides/MicropatternAnalysisTechnique}

\input{slides/MicropatternSawOpcode}

\input{slides/MicropatternAddDetectorToPluginDescriptor}

\input{slides/VerifyPlugin}

\input{slides/MicropatternTestCode}

\input{slides/MicropatternDetectorTest1}

\input{slides/MicropatternAddBugPattern}

\input{slides/MicropatternAddBugPatternToPluginDescriptor}

\input{slides/MicropatternAddBugPatternToMessages}

\input{slides/BugPatternElementStructure}

\input{slides/MicropatternEmitWarning}

\input{slides/MicropatternDetectorTest2}

\input{slides/MicropatternKeepingTrackOfMethod}

\input{slides/MicropatternModifyEmitWarning}

\input{slides/MicropatternAddNewBugPatternToPluginDescriptor}

\input{slides/MicropatternAddNewBugPatternToMessages}

\input{slides/MicropatternDetectorTest3}

\subsection{Dataflow-based detector}

\TitleSlide{Dataflow-based detector}

\input{slides/InconsistentSyncIntro}

\input{slides/DataflowAnalysisConcepts}

%\PlaceholderSlide{FindBugs dataflow infrastructure}{CFGs, BasicBlocks, Edges, InstructionHandles, Locations, exception thrower blocks, handling of jsr instructions}
\input{slides/ControlFlowGraph}

\Slide{Control flow graph pruning}{
  \B
  \item FindBugs attempts to ``prune'' CFGs by removing
        unlikely/impossible control edges
  \item This may create dead code!
    \B
    \item You will notice this when your dataflow
          analysis completes, but some basic blocks
          do not have valid facts (all facts are Top)
    \E
  \E
}

\input{slides/Exceptions}

\input{slides/ExceptionThrowerBlock}

\input{slides/JSRSubroutines}

\input{slides/DataflowAnalysisInFindBugs}

\input{slides/DataflowAnalysisClasses}

%\PlaceholderSlide{Dataflow analysis overview}{Class diagram of base classes}

%\PlaceholderSlide{Important DataflowAnalysis methods}{transfer, transferInstruction, meetInto, etc.}
\input{slides/ImportantDataflowAnalysisMethods}

\input{slides/ImportantDataflowAnalysisMethods2}

%\PlaceholderSlide{LockCountAnalysis (design)}{Count number of locks acquired}
\input{slides/LockCountAnalysisDesign}

%\PlaceholderSlide{LockCount}{The dataflow fact class}
\input{slides/LockCountLattice}
\input{slides/LockCountClass}

%\PlaceholderSlide{LockCountAnalysis}{Implementing the analysis class}
\input{slides/LockCountAnalysisImpl1}

\input{slides/LockCountAnalysisImpl2}

\input{slides/LockCountAnalysisImpl3}

\input{slides/LockCountAnalysisImpl4}

\input{slides/LockCountAnalysisImpl5}

\input{slides/LockCountAnalysisImpl6}

%\PlaceholderSlide{LockCountDataflow}{By convention, every dataflow analysis has a corresponding dataflow class}
\input{slides/LockCountDataflow}

\input{slides/LockCountDataflow2}

%\PlaceholderSlide{LockCountDataflowEngine}{``Analysis engine'': register the analysis with the analysis cache}
\input{slides/LockCountDataflowEngine}

\input{slides/LockCountDataflowEngine2}

\input{slides/LockCountDataflowEngine3}

\input{slides/LockCountDataflowEngine4}

%\PlaceholderSlide{Analysis engine registrar}{The plugin needs an ``analysis engine registrar'' class to register all of its analysis engines}
\input{slides/AnalysisEngineRegistrar}

\input{slides/AnalysisEngineRegistrarImpl}

%\PlaceholderSlide{Testing the analysis}{Build/install plugin, use the TestDataflowAnalysis detector to test}
\input{slides/AddEngineRegistrarElementToPluginDescriptor}

\input{slides/TestLockCountDataflow}

\input{slides/AddInconsistentSyncClass}

\input{slides/FindInconsistentSyncImpl}
\input{slides/FindInconsistentSyncImpl2}
\input{slides/FindInconsistentSyncImpl3}
\input{slides/FindInconsistentSyncImpl4}
\input{slides/FindInconsistentSyncImpl5}
\input{slides/FindInconsistentSyncImpl6}

\input{slides/FindInconsistentSyncAddToPluginDescriptor}
\input{slides/FindInconsistentSyncAddToMessages}

\input{slides/FindInconsistentSyncTestCode}

%\PlaceholderSlide{Detector implementation}{Subclass CFGDetector, accumulate field accesses, finishPass method reports}

%\PlaceholderSlide{Example code}{Show test class, report and DNR cases}

%\PlaceholderSlide{Testing the detector}{Build/install plugin, run from command line}
\input{slides/TestInconsistentSync}

\input{slides/DetectorImplementationWrapup}

%\subsection{Advanced dataflow topics}
\subsection{Advanced topics}

\TitleSlide{Advanced dataflow topics}

%\PlaceholderSlide{FrameDataflowAnalysis}{Uses Frame objects to model local variables and operand stack values}
\Slide{FrameDataflowAnalysis}{
  \B
  \item Base class for analyses that model values in local variables
        and operand stack
  \item Dataflow fact type is subclass of Frame
   \B
   \item The {\em values} in the Frame are what you work with
         (they form the lattice of dataflow values)
   \E
  \item Your main concerns:
    \B
    \item Effect of instructions and control edges on values
          ({\tt transferInstruction} and {\tt edgeTransfer} methods)
    \item Meet function for values
    \E
  \E
}

\Slide{Frame}{
  \B
  \item A stack frame containing slots (local vars and operand stack values)
  \item Each slot contains a {\em value}
  \item Your analysis operates on the values
  \item The Java type you specify for values can
        be immutable
  \item BCEL weirdness:
    \B
    \item BCEL considers {\tt long} and {\tt double} values to
          occupy {\em two} slots
    \item Suggested approach: just put the same dataflow value in both
    \E
  \E
}

\Slide{AbstractFrameModelingVisitor}{
  \B
  \item A base visitor class for modeling the effect of instructons
        on a Frame
    \B
    \item Makes implementing {\tt transferInstruction()} relatively painless
    \E
  \item You only need to override visit methods for instructions
        that are significant for your analysis
    \B
    \item Default implementations of visit methods push a ``default value''
          onto the stack any time stack values are produced
    \item You override {\tt getDefaultValue()} method
          to specify what the default value should be
    \item E.g.: for null pointer analysis, default value is ``not null''
    \E
  \E
}

\Slide{mergeValues()}{
  \B
  \item The {\tt mergeValues()} method in FrameDataflowAnalysis is called
        to compute the meet of the values in a slot of two Frame objects,
        saving the result in the result frame
  \item E.g.: for type analysis, meet of {\tt java.math.BigInteger} and
       {\tt java.math.BigDecimal} is {\tt java.lang.Number}
  \E
}

%\PlaceholderSlide{ValueNumberAnalysis/ValueNumberDataflow}{Answers the question ``are these two values definitely the same''.  Similar to SSA.}
%
%\PlaceholderSlide{TypeAnalysis/TypeDataflow}{Answers the question ``what type of value is this?''}
%
%\PlaceholderSlide{Other useful analyses}{Dominators/PostDominators, LockSet}

\Slide{Useful built-in analyses}{
   FindBugs has a number of built-in dataflow analyses that may
        be useful
  \B
  \item ValueNumberAnalysis/Dataflow
  \item TypeAnalysis/Dataflow
  \item DominatorsAnalysis/Dataflow
  \item LockAnalysis/Dataflow
  \E
}

\frame[containsverbatim]
{
  \frametitle{ValueNumberAnalysis/Dataflow}
{\scriptsize
\begin{verbatim}
ValueNumberDataflow vnaDataflow = analysisCache.getMethodAnalysis(
  ValueNumberDataflow.class, methodDescriptor);
...
ValueNumberFrame vnaFrame = vnaDataflow.getFactAtLocation(location);
\end{verbatim}
}
  \B
  \item Answers question ``do these two Frame slots definitely contain the same value?''
    \B
    \item This is important because Frames often
          contain multiple copies of same value
      \B
      \item E.g., after copying a value from local var to operand stack,
            {\tt dup} instruction, etc.
      \E
    \item Information gained about one value should be propagated to
          all other copies of same value
    \E
  \item Similar to SSA
  \E
}

\frame[containsverbatim]
{
  \frametitle{TypeAnalysis/Dataflow}
{\scriptsize
\begin{verbatim}
TypeDataflow typeDataflow = analysisCache.getMethodAnalysis(
  TypeDataflow.class, methodDescriptor);
...
TypeFrame typeFrame = typeDataflow.getFactAtLocation(location);
\end{verbatim}
}
  \B
  \item Answers question ``what type of value is stored in the Frame slot?''
  \item Values are instances of BCEL {\tt Type} class
  \item Type-inference similar to JVM bytecode verifier
  \E
}

\frame[containsverbatim]
{
  \frametitle{DominatorsAnalysis (and friends)}
{\scriptsize
\begin{verbatim}
DominatorsAnalysis dominatorsAnalysis = analysisCache.getMethodAnalysis(
  DominatorsAnalysis.class, methodDescriptor);
...
BitSet dominators = dominatorsAnalysis.getStartFact(basicBlock);
\end{verbatim}
}
  \B
  \item Get bitset of (integer labels of) BasicBlocks which dominate
        a particular BasicBlock
  \item Also:
    \B
   \item {\tt NonExceptionPostDominatorsAnalysis}
     \B
     \item Ignores all exception control edges
     \E
   \item {\tt NonImplicitExceptionPostDominatorsAnalysis}
     \B
     \item Ignores all ``implicit'' exception edges (e.g., undeclared runtime exceptions)
     \E
    \E
  \E
}

\frame[containsverbatim]
{
  \frametitle{LockAnalysis/Dataflow}
{\scriptsize
\begin{verbatim}
LockDataflow lockDataflow = analysisCache.getMethodAnalysis(
  LockDataflow.class, methodDescriptor);
...
LockSet lockSet = lockDataflow.getFactAtLocation(location);
\end{verbatim}
}
  \B
  \item Set of ValueNumbers which have been locked using
        {\tt monitorenter}
    \B
    \item Counts number of times locked
    \E
  \item Intra-procedural
  \E
}

%\subsection{Interprocedural analysis}

\TitleSlide{Interprocedural analysis}

%\PlaceholderSlide{Interprocedural analysis}{TODO}

\Slide{Interprocedural analysis}{
  \B
  \item FindBugs has some basic support for interprocedural analysis
  \item Recommended approach: compute method summaries in earlier analysis pass,
        use them in later pass
    \B
    \item No real support for iterative analysis
    \item Can fake it by saving information, reloading on next run
    \E
  \item FindBugs orders analysis of classes in pass
        by performing a topological sort on call graph
    \B
    \item Try to analyze referenced class before class that references it
    \item Data computed earlier in pass can be used later in same pass
    \E
  \E
}

\Slide{Implementing an interprocedural analysis}{
  \B
  \item Use two detectors:
    \B
    \item First pass detector computes method summaries
      \B
      \item Guaranteed to see all classes referenced by application
      \item It should implement the NonReportingDetector interface
      \E
    \item Second pass detector uses computed method summaries
      \B
      \item Issue: looking up method summary/summaries at call sites
      \E
    \E
  \item Use detector ordering constraints to ensure the two 
        detectors run in separate analysis passes
  \E
}

\frame[containsverbatim]
{
  \frametitle{Using a database to convey information between passes}
  \B
  \item The first time the first-pass detector visits a class,
        create a {\em database} to store interprocedural information:
{\small
\begin{verbatim}
if (!createdDatabase) {
  MyDatabase db = new MyDatabase();
  analysisCache.eagerlyPutDatabase(MyDatabase.class, db);
  createdDatabase = true;
}
\end{verbatim}
}
  \item Getting the database (in first-pass or second-pass detector):
{\small
\begin{verbatim}
MyDatabase db =
  analysisCache.getDatabase(MyDatabase.class);
\end{verbatim}
}
  \E
}

\frame[containsverbatim]
{
  \frametitle{Populating database in first pass}
Assume the first-pass detector extends CFGDetector:
{\scriptsize
\begin{Verbatim}[commandchars=@\[\]]
protected void visitMethodCFG(MethodDescriptor methodDescriptor, CFG cfg) {
  IAnalysisCache analysisCache = Global.getAnalysisCache();

  [@sl@color[blue]Analyze method, compute summary]

  MyDatabase db = analysisCache.getDatabase(MyDatabase.class);
  db.putSummary(methodDescriptor, [@sl@color[blue]summaryObject]);
}
\end{Verbatim}
}
}

\frame[containsverbatim]
{
  \frametitle{Using information from database in second pass}
{\scriptsize
\begin{Verbatim}[commandchars=@\[\]]
ConstantPoolGen cpg = analysisCache.getClassAnalysis(
  ConstantPoolGen.class, methodDescriptor.getClassDescriptor());
MyDatabase db = analysisCache.getDatabase(MyDatabase.class);

...

// [@sl@color[blue]Analyzing a call site]
Instruction ins = location.getHandle().getInstruction();
if (ins instanceof InvokeInstruction) {
  InvokeInstruction inv = (InvokeInstruction) ins;
  MethodDescriptor calledMethod = BCELUtil.getCalledMethodDescriptor(inv, cpg);
  summary = db.getSummary(calledMethod);
  [@sl@color[blue]Use method summary...]
}
\end{Verbatim}
}
}

\frame
{
  \frametitle{Virtual call sites}
  \B
  \item Database should combine summaries of all methods that implement
        or override the called method
    \B
    \item Can do this lazily as call sites are encountered
    \E
  \item Use Hierarchy class to perform class hierarchy queries
    \B
    \item I.e., which methods implement or override a given method
    \E
  \item In the future:
    \B
    \item Would be nice to have a more general framework in place for
          analyzing virtual call sites
    \item Possibly using a call graph construction algorithm (e.g., RTA)
          to prune possible call targets
    \E
  \E
}
